Package edu.claflin.finder.logic

Class BronKerboschHandler

java.lang.Object

edu.claflin.finder.logic.BronKerboschHandler

public class BronKerboschHandler
extends java.lang.Object

Code for finding maximal clique and maximnal Complete Bipartite of a graph using the Bron-Kerbosch algorithm. https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

Constructor Summary

Constructors

Constructor	Description
BronKerboschHandler()

Method Summary

Modifier and Type	Method	Description
static void	bronKerbosch(java.util.ArrayList<Graph> results, Graph r, Graph p, Graph x, Graph orig)	Recursive helper method to do the above.
static java.util.ArrayList<Graph>	bronKerboschBiclique(Graph graph)	Bipartite Bron Kerbosch algorithm that uses the above to find all complete bipartite graphs within a bipartite graph.
static java.util.ArrayList<Graph>	bronKerboschClique(Graph graph)	Given a graph, finds all complete subgraphs.
static java.util.ArrayList<Graph>	maximumBicliques(Graph graph)	Gets the Maximum Complete Bipartite Graphs by Node count from the input Graph using Bron-Kersboch.
static java.util.ArrayList<Graph>	maximumCliques(Graph graph)	Given a graph, finds all complete subgraphs, and then returns the largest one.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BronKerboschHandler

public BronKerboschHandler()

Method Detail

bronKerbosch

public static void bronKerbosch(java.util.ArrayList<Graph> results,
                                Graph r,
                                Graph p,
                                Graph x,
                                Graph orig)

Recursive helper method to do the above.

Parameters:

results - result list. Passed between recursive calls to create output

r - graph r in wikipedia link

p - graph p in wikipedia link

x - graph x in wikipedia link

orig - original Graph containing edges

bronKerboschClique

public static java.util.ArrayList<Graph> bronKerboschClique(Graph graph)

Given a graph, finds all complete subgraphs.

Parameters:

graph - the graph

Returns:

an ArrayList of complete subgraphs, unordered

bronKerboschBiclique

public static java.util.ArrayList<Graph> bronKerboschBiclique(Graph graph)

Bipartite Bron Kerbosch algorithm that uses the above to find all complete bipartite graphs within a bipartite graph. This is done by adding edges between every node in both groups, using the above algorithm, and removing all the added edges later on. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!

Parameters:

graph - the bipartite graph

Returns:

array list of bipartite graphs

maximumCliques

public static java.util.ArrayList<Graph> maximumCliques(Graph graph)

Given a graph, finds all complete subgraphs, and then returns the largest one.

Parameters:

graph - the graph

Returns:

the largest complete subgraph (clique)

maximumBicliques

public static java.util.ArrayList<Graph> maximumBicliques(Graph graph)

Gets the Maximum Complete Bipartite Graphs by Node count from the input Graph using Bron-Kersboch.

Parameters:

graph - the input Graph

Returns:

the Maximum Complete Bipartite Graphs